import matplotlib.pyplot as plt
import networkx as nx
import random
import numpy as np
#import sys, os
#sys.path.append(os.pardir)  # 为了导入父目录而进行的设定
#from ch_06 import _00SetFunc as sf


#绘制无向图函数
def drawgraph(E):
    G=nx.Graph()
    G.add_edges_from(E)
    nx.draw(G,node_size=200,node_color='r',with_labels=True,font_color='w')
    plt.show()
    return

#绘制有向图函数
def drawdigraph(E):
    G=nx.DiGraph()
    G.add_edges_from(E)
    nx.draw(G,node_size=200,node_color='r',with_labels=True,font_color='w')
    plt.show()
    return

def Cartesianproduct(X,Y):#以结点集V构成笛卡尔集XY
    XY=list({})
    for x in X:
        for y in Y:
            if x!=y:
                XY.append((x,y))
    return XY


#构造G（m,n）图算法
#以结点集V构成笛卡尔集XY
#在笛卡尔集XY上随机取n条边
def creategraph(m,n):
    global V,XY
    V=range(m)
    XY=Cartesianproduct(V,V)#产生边集
    E=random.sample(XY,n)
    E=set(E)
    for (u,v) in E:
        if(v,u) not in E:
            E=E|{(v,u)}
        V=set(V)
        return [V,E]
    
def createdigraph(m,n):
    global V,XY
    V=range(m)
    XY=Cartesianproduct(V,V)
    E=random.sample(XY,n)
    V=set(V)
    E=set(E)
    return [V,E]
    
#构建MxN图
def MNgraph(m,n):
    V=set({})
    E=set({})
    for i in range(m):#构建行，同时构建节点集V
        for j in range(n-1):
            u=i*n+j
            v=u+1
            V=V|{u,v}
            E=E|{(u,v)}
    for i in range(m-1):#构建列
        for j in range(n):
            u=i*n+j
            v=u+n
            E=E|{(u,v)}
    return [V,E]

#生成加权图
def weightedgraph(V0,E0,W0):
    V=V0
    E=set({})
    for(u,v)in E0:
        w=random.randint(1,W0)#生成1~w0之间的随机整数
        E=E|{(w,u,v)}
    return [V,E]

#判断是否为图
def isgraph(V,E):
    tv=True
    for(u,v)in E:
        tv=tv and (u in V) and (v in V)
    return tv

#计算入度与出度
def degreeset(V,E):
    V=list(V)
    di=[0]*len(V)
    do=[0]*len(V)
    d=[0]*len(V)
    for(u,v)in E:
        di[V.index(v)]+=1
        do[V.index(u)]+=1
        d[V.index(u)]+=1
        d[V.index(v)]+=1
    return [d,di,do]

#构建完全图，集合操作方法
def completegraphset(n):
    V=set({})
    E=set({})
    for i in range(n):
        V=V|{i}
        for j in range(n):
            if(i!=j):
                E=E|{(i,j)}
    return (V,E)

#构建完全图，集合函数方法
def completegraphsetfunc(n):
    V=set({})
    E=set({})
    for i in range(n):
        V.add(i)
        for j in range(n):
            E.add((i,j))
    return (V,E)

#完全图边集用列表表示
def completegraphlist(n):
    V=set({})
    E=[]
    for i in range(n):
        V=V|{i}
        for j in range(n):
            E=E+[[i,j]]
    return [V,E]

#构建圈图,边集用集合表示
def cyclicgraphset(n):
    V={0}
    E=set({})
    for k in range(1,n):
        V=V|{k}
        E=E|{(k-1,k)}
    E=E|{(n-1,0)}
    return (V,E)

#构建圈图,边集用列表表示
def cyclicgraphlist(n):
    V={0}
    E=[]
    for k in range(1,n):
        V=V|{k}
        E=E+[[k-1,[k]]]
    E=E+[[n-1],[0]]
    return (V,E)

#轮图构建方法，边集用集合表示
def wheelgraphset(n):
    V={0,1}
    E=set({})
    for k in range(1,n):
        V=V|{k}
        E=E|{(0,k)}
        E=E|{(k-1,k)}
    E=E|{(n-1,0)}
    return (V,E)

#轮图构建方法，边集用列表表示
def wheelgraphlist(n):
    V={0,1}
    E=[]
    E0=[]
    for k in range(1,n):
        V=V|{k}
        E0=E0+[k]
        E=E+[[k-1,[k]]]
    E=E+[[n-1,[1]]]+[[0,E0]]
    e=[0,[1]]
    E.remove(e)
    return (V,E)

#完全二分图构建,边集用集合表示
def completebigraphset(m,n):
    Vx=set(range(m))
    Vy=set(range(n))
    V0=set({})
    V1=set({})
    E=set({})
    for u in Vx:
        for v in Vy:
            x='x'+str(u)
            y='y'+str(v)
            V0=V0|{x}
            V1=V1|{y}
            E=E|{(x,y)}
    return [V0,V1,E]

#完全二分图构建,边集用列表表示
def completebigraphlist(m,n):
    Vx=set(range(m))
    Vy=set(range(n))
    V0=set({})
    V1=set({})
    E=list({})
    for u in Vx:
        for v in Vy:
            x='x'+str(u)
            y='y'+str(v)
            V0=V0|{x}
            V1=V1|{y}
            E=E+[[x,y]]
    return [V0,V1,E]

#0-1序列图构建,边集由集合表示
def sequence01graphset(m):
    V=set({})
    E=set({})
    n=2**m
    for i in range(n):
        V=V|{i}
        j=(2*i)%n
        E=E|{(i,j)}
        j=(2*i+1)%n
        E=E|{(i,j)}
        j=(2*i+1)%n
        E=E|{(i,j)}
    return (V,E)

#0-1序列图构建,边集由列表表示
def sequence01graphlist(m):
    V=set({})
    E=[]
    n=2**m
    for i in range(n):
        V=V|{i}
        j0=(2*i)%n
        j1=(2*i+1)%n
        E=E+[[i,[j0,j1]]]
    return (V,E)

#立方体图构建,边集用集合表示
def ncubegraphset(m):
    V=set({})
    E=set({})
    n=2**m
    for i in range(n):
        V=V|{i}
        u=1
        k=0
        while(k<m):
            if(i&u==0):
                j=i|u
            else:
                j=i-u
            E=E|{(i,j)}
            u=u*2
            k=k+1
    return (V,E)

#立方体图构建,边集用列表表示
def ncubegraphlist(m):
    V=set({})
    E=[]
    n=2**m
    for i in range(n):
        V=V|{i}
        u=1
        k=0
        E0=[]
        while(k<m):
            if(i&u==0):
                j=i|u
            else:
                j=i-u
            E0=E0+[j]
            u=u*2
            k=k+1
        E=E+[[i,E0]]
    return (V,E)

#判断子图
def issubgragh(V,E,Vs,Es):
    tv=(Vs<=V) and (Es<=E)
    return tv

#判断真子图
def ispropersubgraph(V,E,Vs,Es):
    tv=((Vs<=V) and(Es<= E)) and((Vs<V)or(Es<E))
    return tv

#判断生成子图
def isspanningsubgraph(V,E,Vs,Es):
    tv=((Vs<=V) and(Es<=E))and((Vs== V) or(Es<= E))
    return tv

#判断导出子图
def isinducedsubgraph(V,E,Vs,Es):
    tv=((Vs<=V)and(Es<=E))
    for (u,v) in E:
        tv=tv and ((not((u in Vs)and(v in Vs)))or((u,v) in Es))
    return tv

#将图变换为矩阵
def graph2array(V,E):
    n=len(V)
    A=np.zeros((n,n),dtype='int')
    A=np.array(A)
    for i in range(n):
        for j in range(n):
            if (i,j) in E:
                A[i,j]=1
    return A

#生成可达矩阵
def reachabilityarray(A,n):
    m=len(A)
    I=np.array(np.eye(m,dtype='int'))
    Ai=I+A
    An=Ai**(n-1)
    R=np.zeros((m,m),dtype='int')
    for i in range(m):
        for j in range(m):
            if An[i,j]!=0:
                R[i,j]=1 
            else:
                R[i,j]=0
    return R

#构建路径边数为n的所有路径
def pathset(path0,E):
    path=set({})
    for p0 in path0:
        y=p0[-1]
        for (u,v)in E:
            if u==v:
                continue 
            p=p0
            if(u==y):
                p=p+tuple([v])
                path=path| {p}
    return path
    
def basicpathset(path0,E):
    path=set({})
    for pk in path0:
        x=pk[-1]
        for (u,v) in E:
            if u==v:
                continue 
            p=pk
            #print(p,x,(u==x and (v not in pk)))
            if (u==x and (v not in pk)):
                p=p+tuple([v])
            path=path|{p}
    return path

#构建连通图
def connectedgraph(V, E, V0, E0):
    Vc=V0
    Ec=E0
    while E !=set({}):
        n=len(Ec)
        for (u,v)in E:
            if (u,v) not in Ec and (u in Vc or v in Vc):
                Vc=Vc |{u,v}
                Ec=Ec |{(u,v)}
        if len(Ec)== n:
            break 
    return [Vc,Ec]

#判断是否为连通图   
def isconnectedgraph(V,E):
    V=list(V)
    E=list(E)
    (u,v)=E[0]
    V0={u,v}
    E0={(u,v)}
    [Vc,Ec]=connectedgraph(V,E,V0,E0)
    tv=(set(V)==set(Vc))&(set(Ec)==set(E))
    return tv




